{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Value After Replacing With Sum of Prime Factors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使用质因数之和替换后可以取到的最小值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数 <code>n</code> 。</p>\n",
    "\n",
    "<p>请你将 <code>n</code> 的值替换为 <code>n</code> 的 <strong>质因数</strong> 之和，重复这一过程。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>注意，如果 <code>n</code> 能够被某个质因数多次整除，则在求和时，应当包含这个质因数同样次数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回<em> </em><code>n</code><em> </em>可以取到的最小值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 15\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>最开始，n = 15 。\n",
    "15 = 3 * 5 ，所以 n 替换为 3 + 5 = 8 。\n",
    "8 = 2 * 2 * 2 ，所以 n 替换为 2 + 2 + 2 = 6 。\n",
    "6 = 2 * 3 ，所以 n 替换为 2 + 3 = 5 。\n",
    "5 是 n 可以取到的最小值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>最开始，n = 3 。\n",
    "3 是 n 可以取到的最小值。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-value-after-replacing-with-sum-of-prime-factors](https://leetcode.cn/problems/smallest-value-after-replacing-with-sum-of-prime-factors/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-value-after-replacing-with-sum-of-prime-factors](https://leetcode.cn/problems/smallest-value-after-replacing-with-sum-of-prime-factors/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['15', '3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x, s, i = n, 0, 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x /= i\n",
    "                \n",
    "                i += 1\n",
    "            \n",
    "            if x > 1:\n",
    "                s += x\n",
    "            if s == n:\n",
    "                return int(s)\n",
    "            \n",
    "            n = s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        def get_sushu(max_num):\n",
    "            sushu = [2,3,5]\n",
    "            i = 1\n",
    "            while sushu[-1]**2<=max_num:\n",
    "                n1 = 6*i+1\n",
    "                n2 = 6*i+5\n",
    "                flag1=flag2=1\n",
    "                for s in sushu:\n",
    "                    if s**2>n2:\n",
    "                        break\n",
    "                    if n1%s==0:\n",
    "                        flag1=0\n",
    "                    if n2%s==0:\n",
    "                        flag2=0\n",
    "                    if not flag1 and not flag2:\n",
    "                        break\n",
    "                if flag1:\n",
    "                    sushu.append(n1)\n",
    "                if flag2:\n",
    "                    sushu.append(n2)\n",
    "            \n",
    "            return sushu\n",
    "        \n",
    "        # sushu = get_sushu(n)\n",
    "        \n",
    "        while 1:\n",
    "            last = n\n",
    "            tmp = 0\n",
    "            s = 2\n",
    "            while s**2<=n:                \n",
    "                while n%s==0:\n",
    "                    n = n//s\n",
    "                    tmp+=s\n",
    "                s+=1\n",
    "            if n!=1:\n",
    "                tmp += n\n",
    "            if tmp==last:\n",
    "                return last\n",
    "            else:\n",
    "                n = tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x, s, i = n, 0, 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1: s += x\n",
    "            if s == n: return n\n",
    "            n = s\n",
    "\n",
    "                    \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x = n\n",
    "            s = 0\n",
    "            i = 2\n",
    "            while i*i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1:\n",
    "                s += x\n",
    "            if s == n:\n",
    "                break\n",
    "            else:\n",
    "                n = s\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x, s, i = n, 0, 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1: s += x\n",
    "            if s == n: return n\n",
    "            n = s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x, s, i = n, 0, 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1: s += x\n",
    "            if s == n: return n\n",
    "            n = s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while 1:\n",
    "            tem, ans, i = n, 0, 2\n",
    "            while i * i <= tem:\n",
    "                while tem % i == 0:\n",
    "                    tem //= i\n",
    "                    ans += i\n",
    "                i += 1\n",
    "            if tem > 1: ans += tem\n",
    "            if ans == n: return ans\n",
    "            n = ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # use a global vector to save the found prime number might be a good choice\n",
    "    def is_prime(self, n:int) -> int:\n",
    "        if n == 2 or n == 3 or n == 5 or n == 7 or n == 11:\n",
    "            return True\n",
    "        loop_stop = int(n/2)+1\n",
    "        for i in range(2,loop_stop):\n",
    "            if mod(n,i) == 0:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        if self.is_prime(n):\n",
    "            return n\n",
    "        sum = 0\n",
    "        rest = n\n",
    "        while not self.is_prime(rest):\n",
    "            loop_stop = int(rest/2)+1\n",
    "            for i in range(2,loop_stop):\n",
    "                if self.is_prime(i) and mod(rest,i) == 0:\n",
    "                    sum += i\n",
    "                    rest =int(rest/i)\n",
    "                    break\n",
    "        sum += rest\n",
    "        if sum == n:\n",
    "            return sum\n",
    "        return self.smallestValue(sum)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x, s, i, = n, 0, 2\n",
    "            while i * 1 <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1:\n",
    "                s += x\n",
    "            if s == n:\n",
    "                return n\n",
    "            n = s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        def isPrime(n):\n",
    "            if n < 5:\n",
    "                return True\n",
    "            if n % 6 not in (1, 5):\n",
    "                return False\n",
    "            for i in range(5, isqrt(n) + 1, 6):\n",
    "                if n % i == 0 or n % (i + 2) == 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        while not isPrime(n):\n",
    "            total = 0\n",
    "            for i in range(2, isqrt(n) + 1):\n",
    "                while n > i and n % i == 0:\n",
    "                    n //= i\n",
    "                    total += i\n",
    "            n += total\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x, s, i = n, 0, 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1: s += x\n",
    "            if s == n: return n\n",
    "            n = s\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.N = 0\n",
    "    \n",
    "    def judge(self, n):\n",
    "        i = 2\n",
    "        while i < n/2:\n",
    "            if n%i == 0:\n",
    "                return 0\n",
    "            i=i+1\n",
    "        return 1\n",
    "    \n",
    "    def smallest(self, n):\n",
    "        i = 2\n",
    "        while i < n+1 :\n",
    "            if n%i ==0:\n",
    "                self.N= self.N+i\n",
    "                return self.smallest(n/i)\n",
    "            i=i+1\n",
    "        T = self.N\n",
    "        self.N = 0\n",
    "        return T\n",
    "    \n",
    "    def smallestValue(self, n):\n",
    "        self.N = 0\n",
    "        if self.judge(n)==0:\n",
    "            return self.smallestValue(self.smallest(n))\n",
    "        else:\n",
    "            return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        @cache\n",
    "        def isPrime(n):\n",
    "            if n in (2, 3, 4):\n",
    "                return True\n",
    "            if n % 6 not in (1, 5):\n",
    "                return False\n",
    "            for i in range(5, isqrt(n) + 1, 6):\n",
    "                if n % i == 0 or n % (i + 2) == 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        while not isPrime(n):\n",
    "            total = 0\n",
    "            for i in range(2, isqrt(n) + 1):\n",
    "                while n > i and n % i == 0:\n",
    "                    n //= i\n",
    "                    total += i\n",
    "            n += total\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        ans=float('inf')\n",
    "        sum1=n\n",
    "        while True:\n",
    "            sign=sum1\n",
    "            temp=sum1\n",
    "            sum1 = 0\n",
    "            for i in range(2,sign+1):\n",
    "                num=0\n",
    "                while temp%i==0:\n",
    "                    temp//=i\n",
    "                    num+=1\n",
    "                sum1+=num*i\n",
    "            if sum1 != 0:\n",
    "                ans = min(ans, sum1)\n",
    "            if sum1==sign:\n",
    "                break\n",
    "        return ans\n",
    "            \n",
    "                    \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        def primeFactors(n):\n",
    "            res = []\n",
    "            for i in range(2, int(n ** 0.5) + 1):\n",
    "                while n % i == 0:\n",
    "                    res.append(i)\n",
    "                    n //= i\n",
    "            if n >= 2:\n",
    "                res.append(n)\n",
    "            return sum(res)\n",
    "        while n != primeFactors(n):\n",
    "            n = primeFactors(n)\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        \n",
    "        while True:\n",
    "            x, s, i = n, 0, 2\n",
    "            # 不断循环，计算 nnn 的质因数之和。\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1: s += x\n",
    "            if s == n: return n # 对勾函数 x + x / i >= x 等于的时候为质因数之和的最小值\n",
    "            n = s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x = n\n",
    "            s = 0\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i \n",
    "                    x //= i \n",
    "                i += 1\n",
    "            if x > 1: s += x\n",
    "            if s == n: return n\n",
    "            n = s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        result = 0\n",
    "        while n and result != n:\n",
    "            result = n\n",
    "            k = (n & (-n)).bit_length() - 1\n",
    "            m, n, i = k << 1, n >> k, 3\n",
    "            while i * i <= n:\n",
    "                while not n % i:\n",
    "                    m += i\n",
    "                    n //= i\n",
    "                i += 2\n",
    "            n = m + n * (n > 1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        def f(n):\n",
    "            k = (n & (-n)).bit_length() - 1\n",
    "            result, n, i = k << 1, n >> k, 3\n",
    "            while i * i <= n:\n",
    "                while not n % i:\n",
    "                    result += i\n",
    "                    n //= i\n",
    "                i += 2\n",
    "            return result and result + n * (n > 1)\n",
    "        result = 0\n",
    "        while n and result != n:\n",
    "            result = n\n",
    "            n = f(n)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x, s, i = n, 0, 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1: s += x\n",
    "            if s == n: return n\n",
    "            n = s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        def foo(n):\n",
    "            l = []\n",
    "            i = 2\n",
    "            while i < n:\n",
    "                if n % i != 0:\n",
    "                    i = i + 1\n",
    "                else:\n",
    "                    n = n // i\n",
    "                    l.append(i)\n",
    "            if n > 1:\n",
    "                l.append(n)\n",
    "            return l\n",
    "\n",
    "        if n == 4:\n",
    "            return 4\n",
    "        n = sum(foo(n))\n",
    "        flag = foo(n)\n",
    "        while len(flag) > 1:\n",
    "            n = sum(foo(n))\n",
    "            flag = foo(n)\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x, s, i = n, 0, 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1: s += x\n",
    "            if s == n: return n\n",
    "            n = s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x, s, i = n, 0, 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1: s += x\n",
    "            if s == n: return n\n",
    "            n = s      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x = n\n",
    "            s = 0\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1:\n",
    "                s += x\n",
    "            if s == n:\n",
    "                return n\n",
    "            n = s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        # 定义一个求质因数和的函数\n",
    "        def get_prime_factor_sum(n: int) -> int:\n",
    "            i = 2\n",
    "            sum_val = 0\n",
    "            # 寻找n的质因数\n",
    "            while i * i <= n:\n",
    "                while n % i == 0:\n",
    "                    sum_val += i\n",
    "                    n //= i\n",
    "                i += 1\n",
    "            # 如果n大于1，说明它自身就是一个质数\n",
    "            if n > 1:\n",
    "                sum_val += n\n",
    "            return sum_val\n",
    "        \n",
    "        # 不断地将n更新为它的质因数之和\n",
    "        while True:\n",
    "            prime_sum = get_prime_factor_sum(n)\n",
    "            # 如果质因数和与n相同，说明n已经是质数或1，停止循环\n",
    "            if prime_sum == n:\n",
    "                break\n",
    "            n = prime_sum\n",
    "        \n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        su = n\n",
    "        last = n\n",
    "        while su:\n",
    "            i = 2\n",
    "            n = su\n",
    "            su = 0\n",
    "            last = n\n",
    "            while i * i <= n:\n",
    "                if n % i == 0:\n",
    "                    su += i\n",
    "                    n //= i\n",
    "                    while n % i == 0:\n",
    "                        su += i\n",
    "                        n //= i\n",
    "                i += 1\n",
    "            # print(su, n)\n",
    "            if n > 1:\n",
    "                su += n\n",
    "            # print(su, n)\n",
    "            if su == last:\n",
    "                return su\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            i = 2\n",
    "            s = 0\n",
    "            tmp = n\n",
    "            while i * i <= n:\n",
    "                while n % i == 0:\n",
    "                    n //= i\n",
    "                    s += i\n",
    "                i += 1\n",
    "            \n",
    "            if s == 0:\n",
    "                return n\n",
    "            if n > 1:\n",
    "                s += n\n",
    "            if s == tmp:\n",
    "                return s\n",
    "            n = s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def smallestValue(self, n: int) -> int:\n",
    "       while True:\n",
    "           x, s, i = n, 0, 2\n",
    "           while i * i <= x:\n",
    "               while x % i == 0:\n",
    "                   s += i\n",
    "                   x //= i\n",
    "               i += 1\n",
    "           if x > 1: s += x\n",
    "           if s == n: return n\n",
    "           n = s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x, s, i = n, 0, 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1: s += x\n",
    "            if s == n: return n\n",
    "            n = s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        nn = n\n",
    "        ans = 0\n",
    "        for i in range(2, int(sqrt(n + 0.5)) + 1):\n",
    "            while n % i == 0:\n",
    "                ans += i\n",
    "                n //= i\n",
    "        if n > 1:\n",
    "            ans += n\n",
    "        if ans == nn:\n",
    "            return nn\n",
    "        return self.smallestValue(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x,s,i = n,0,2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1:\n",
    "                s += x\n",
    "            if s == n:\n",
    "                return n\n",
    "            n = s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def smallestValue(self, n: int) -> int:\n",
    "    if n == 4: return 4\n",
    "    while not self.check(n):\n",
    "      sum, i = 0, 2\n",
    "      while n > 1:\n",
    "        if n % i == 0:\n",
    "          sum += i\n",
    "          n //= i\n",
    "        else:\n",
    "          i += 1\n",
    "      n = sum\n",
    "    return n\n",
    "  def check(self, n: int) -> bool:\n",
    "    if n == 1 or n == 2 or n == 3 or n == 5 or n == 7 or n == 11 or n == 13 or n == 17:\n",
    "      return True\n",
    "    for i in range(2, n):\n",
    "      if n % i == 0:\n",
    "        return False\n",
    "    return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        primes = [2]\n",
    "        for x in range(3, n+1):\n",
    "            if x * x > n: break\n",
    "            for p in primes:\n",
    "                if x % p == 0: break\n",
    "            else:\n",
    "                primes.append(x)\n",
    "        lastN = 0\n",
    "        while n != lastN:\n",
    "            lastN = n\n",
    "            newN = 0\n",
    "            for p in primes:\n",
    "                while n > 1:\n",
    "                    nn, r = divmod(n, p) \n",
    "                    if r: break\n",
    "                    n = nn\n",
    "                    newN += p\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                if not newN:\n",
    "                    return n\n",
    "                newN += n\n",
    "            n = newN\n",
    "        return lastN\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "         while True:\n",
    "            x, ans, i = n, 0, 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    ans += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1: ans += x\n",
    "            if ans == n: return n\n",
    "            n = ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x, s, i = n, 0, 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1: s += x\n",
    "            if s == n: return n\n",
    "            n = s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x, s = n, 0\n",
    "            for i in range(2, isqrt(x) + 1):\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "            if x > 1: \n",
    "                s += x\n",
    "            if s == n: \n",
    "                return n\n",
    "            n = s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        def cal(num):\n",
    "            res = 0\n",
    "            f = 2\n",
    "            for f in range(2,int(sqrt(num))+1):\n",
    "                while num%f == 0:\n",
    "                    res += f\n",
    "                    num //= f\n",
    "            if num > 1:\n",
    "                res += num\n",
    "            return res\n",
    "        \n",
    "        while (nxt := cal(n)) != n:\n",
    "            # print(n,nxt)\n",
    "            n = nxt\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while 1:\n",
    "            x, s , i = n, 0 , 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1: s += x    #剩余上半区的因数\n",
    "            if s == n: return s\n",
    "            n = s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@staticmethod\n",
    "def get_prime_factor(x):\n",
    "    # 模板：质因数分解最多支持 1**12\n",
    "    ans = []\n",
    "    j = 2\n",
    "    while j * j <= x:\n",
    "        if x % j == 0:\n",
    "            c = 0\n",
    "            while x % j == 0:\n",
    "                x //= j\n",
    "                c += 1\n",
    "            ans.append([j, c])\n",
    "        j += 1\n",
    "    if x > 1:\n",
    "        ans.append([x, 1])\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            res = get_prime_factor(n)\n",
    "            nex = 0\n",
    "            for num, va in res:\n",
    "                nex += num*va\n",
    "            # 坑点，如果不会再变化则停止分解\n",
    "            if nex == n:\n",
    "                break\n",
    "            n = nex\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        # n 转化为质数之和是会一直变小的\n",
    "        while True:\n",
    "            x = n\n",
    "            s = 0\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0: # 这里i一定为质数\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1: s += x\n",
    "            if s == n: return n\n",
    "            n = s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        ans=float('inf')\n",
    "        sum1=n\n",
    "        while True:\n",
    "            sign=sum1\n",
    "            temp=sum1\n",
    "            sum1 = 0\n",
    "            for i in range(2,temp+1):\n",
    "                while temp%i==0:\n",
    "                    temp//=i\n",
    "                    sum1+=i\n",
    "            if sum1 != 0:\n",
    "                ans = min(ans, sum1)\n",
    "            if sum1==sign:\n",
    "                break\n",
    "        return ans\n",
    "            \n",
    "                    \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        while True:\n",
    "            x = n\n",
    "            s = 0\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1 : s += x\n",
    "            if s == n : return n\n",
    "            n = s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        #暴力解决\n",
    "\n",
    "        while True:\n",
    "            x,s,i = n,0,2\n",
    "            while i*i <= x:\n",
    "                while x%i == 0:\n",
    "                    s += i\n",
    "                    x //= i\n",
    "\n",
    "                i += 1\n",
    "            if x>1: s += x\n",
    "            if s == n:return n\n",
    "\n",
    "            n = s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "         # 构造一个判断n是否为质数的函数\n",
    "        def issushu(n):\n",
    "            for i in range(2,int(n**0.5)+1):\n",
    "                if(n%i==0):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        while(1):\n",
    "            tmp=0\n",
    "            while not issushu(n):\n",
    "                for i in range(2,int(n**0.5)+1):\n",
    "                    if(issushu(i) and n%i==0):\n",
    "                        tmp+=i\n",
    "                        n=int(n/i)\n",
    "                        break\n",
    "            tmp+=n\n",
    "            if issushu(tmp) or tmp==4:\n",
    "                return tmp\n",
    "                break\n",
    "            else:\n",
    "                n=tmp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def smallestValue(self, n: int) -> int:\n",
    "    if n == 4: return 4\n",
    "    while not self.check(n):\n",
    "      sum, i = 0, 2\n",
    "      while n > 1:\n",
    "        if n % i == 0:\n",
    "          sum += i\n",
    "          n //= i\n",
    "        else:\n",
    "          i += 1\n",
    "      n = sum\n",
    "    return n\n",
    "  def check(self, n: int) -> bool:\n",
    "    if n == 1 or n == 2 or n == 3 or n == 5 or n == 7 or n == 11 or n == 13 or n == 17:\n",
    "      return True\n",
    "    for i in range(2, n):\n",
    "      if n % i == 0:\n",
    "        return False\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "  def smallestValue(self, n: int) -> int:\n",
    "    if n == 4: return 4\n",
    "    while not self.check(n):\n",
    "      sum, i = 0, 2\n",
    "      while n > 1:\n",
    "        if n % i == 0:\n",
    "          sum += i\n",
    "          n //= i\n",
    "        else:\n",
    "          i += 1\n",
    "      n = sum\n",
    "    return n\n",
    "  def check(self, n: int) -> bool:\n",
    "    if n == 1 or n == 2 or n == 3 or n == 5 or n == 7 or n == 11 or n == 13 or n == 17:\n",
    "      return True\n",
    "    for i in range(2, n):\n",
    "      if n % i == 0:\n",
    "        return False\n",
    "    return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 5 + 1\n",
    "is_prime = [True] * MX\n",
    "is_prime[1] = False\n",
    "is_prime[0] = False\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        if is_prime[n] or n == 4: return n\n",
    "        \n",
    "        def find(n):\n",
    "            for i in range(2,n-1):\n",
    "                if is_prime[i]:\n",
    "                    if n % i == 0:\n",
    "                        yu = n // i\n",
    "                        if is_prime[yu]:\n",
    "                            return i + yu\n",
    "                        else:\n",
    "                            return i + find(yu)\n",
    "        \n",
    "        while not is_prime[n]:\n",
    "            n = find(n)\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "p=[True]*100001\n",
    "primes=[]\n",
    "for i in range(2,100001):\n",
    "    if p[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i*i,100001,i):\n",
    "            p[j]=False\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        def solve(a:int)->int:\n",
    "            res=0\n",
    "            for i in primes:\n",
    "                if i>a:break\n",
    "                while a%i==0:\n",
    "                    res +=i\n",
    "                    a /=i\n",
    "            return res\n",
    "        while n not in primes:\n",
    "            \n",
    "            cur=solve(n)\n",
    "            if cur==n: return cur\n",
    "            n=cur\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "p=[True]*100001\n",
    "primes=[]\n",
    "for i in range(2,100001):\n",
    "    if p[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i*i,100001,i):\n",
    "            p[j]=False\n",
    "class Solution:\n",
    "    def smallestValue(self, n: int) -> int:\n",
    "        def solve(a:int)->int:\n",
    "            res=0\n",
    "            for i in primes:\n",
    "                if i>a:break\n",
    "                while a%i==0:\n",
    "                    res +=i\n",
    "                    a /=i\n",
    "            return res\n",
    "        while True:\n",
    "            \n",
    "            cur=solve(n)\n",
    "            if cur==n: return cur\n",
    "            n=cur\n",
    "        return n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
